import io, os
t = int(input())
for tidx in range(t):
input()
n, m = [int(x) for x in input().split()]
d = dict()
for i in range(n):
st = input()
for j in range(m-1):
d[st[j:(j+2)]] = (j, j+1, i)
for j in range(m-2):
d[st[j:(j+3)]] = (j, j+2, i)
st = input()
segments = [(0,0,0)]*m
bools = [False]*m
for i in range(m):
if i==1 or (i>1 and bools[i-2]):
if st[(i-1):(i+1)] in d:
segments[i] = d[st[(i-1):(i+1)]]
bools[i] = True
if i==2 or (i>2 and bools[i-3]):
if st[(i-2):(i+1)] in d:
segments[i] = d[st[(i-2):(i+1)]]
bools[i] = True
if bools[m-1]:
out = []
idx = m-1
while idx>0:
out.append(segments[idx])
idx -= 1+segments[idx][1]-segments[idx][0]
k = len(out)
print(k)
for i in range(k-1,-1,-1):
print(out[i][0]+1, out[i][1]+1, out[i][2]+1)
else: print(-1)
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include<algorithm>
using namespace std;
using int64 = long long;
using uint = unsigned int;
void solve(){
int n, m;
cin>>n>>m;
unordered_map<string, vector<int>> mp;
mp.rehash(2 * n);
string s;
for(int i = 0; i < n; i++){
cin>>s;
for(int j = 0; j + 1 < m; j++){
string tmp = s.substr(j, 2);
mp[tmp] = {j + 1, j + 2, i + 1};
if(j + 2 < m){
tmp += s[j + 2];
mp[tmp] = {j + 1, j + 3, i + 1};
}
}
}
cin>>s;
vector<int> dp(m + 1, 0);
dp[0] = 1;
for(int i = 0; i < m - 1; ++i){
if(!dp[i]) continue;
string tmp = s.substr(i, 2);
if(mp.count(tmp)) dp[i + 2] = 1;
if(i < m - 2) {
tmp += s[i + 2];
if(mp.count(tmp)) dp[i + 3] = 1;
}
}
if(dp[m]){
vector<vector<int>> res;
int l = m;
while(l > 0){
if(dp[l - 2]){
string tmp = s.substr(l - 2, 2);
res.push_back(mp[tmp]);
l -= 2;
}
else{
string tmp = s.substr(l - 3, 3);
res.push_back(mp[tmp]);
l -= 3;
}
}
cout<<res.size()<<'\n';
for(int i = res.size() - 1; i >= 0; --i){
cout<<res[i][0]<<' '<<res[i][1]<<' '<<res[i][2]<<'\n';
}
}
else{
cout<<-1<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// int t = 1;
int t;
cin>>t;
while(t--){
solve();
}
return 0;
} 94. Binary Tree Inorder Traversal | 101. Symmetric Tree |
77. Combinations | 46. Permutations |
226. Invert Binary Tree | 112. Path Sum |
1556A - A Variety of Operations | 136. Single Number |
169. Majority Element | 119. Pascal's Triangle II |
409. Longest Palindrome | 1574A - Regular Bracket Sequences |
1574B - Combinatorics Homework | 1567A - Domino Disaster |
1593A - Elections | 1607A - Linear Keyboard |
EQUALCOIN Equal Coins | XOREQN Xor Equation |
MAKEPAL Weird Palindrome Making | HILLSEQ Hill Sequence |
MAXBRIDGE Maximise the bridges | WLDRPL Wildcard Replacement |
1221. Split a String in Balanced Strings | 1002. Find Common Characters |
1602A - Two Subsequences | 1555A - PizzaForces |
1607B - Odd Grasshopper | 1084A - The Fair Nut and Elevator |
1440B - Sum of Medians | 1032A - Kitchen Utensils |